package newBee.class2;

import common.ArrayUtils;

/**
 * https://leetcode.cn/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/
 * 望远镜中最高的海拔
 */
public class Code03_maxAltitude {
    public static void main(String[] args) {
        int[] heights = {14, 2, 27, -5, 28, 13, 39};
        int limit = 3;
        int[] ans = maxAltitude(heights, limit);
        ArrayUtils.printArr(ans);
    }

    public static int[] maxAltitude(int[] heights, int limit) {
        if (heights == null || limit == 0) {
            return heights;
        }
        int h = 0, t = 0, n = heights.length;
        int[] deque = new int[n];
        for (int i = 0; i < limit - 1; i++) {
            while (h < t && heights[deque[t - 1]] <= heights[i]) {
                t--;
            }
            deque[t++] = i;
        }
        int[] ans = new int[n - limit + 1];
        int l = 0, r = limit - 1;
        for (; r < n; l++, r++) {
            while (h < t && heights[deque[t - 1]] <= heights[r]) {
                t--;
            }
            deque[t++] = r;
            ans[l] = heights[deque[h]]; // 去窗口最大值
            if (l == deque[h]) { // 当l是最大值时，需要h++,因为窗口需要右移
                h++;
            }
        }

        return ans;
    }
}
